package com.lsa.letcode.the1.twosum;

import java.util.Arrays;
import java.util.Comparator;


public class Solution {
    public int[] twoSum(int[] input, int target) {
    	int[] result = new int[2];
    	class Number {
    		int n;
    		int idx;
			Number(int n, int idx) {
				this.n = n;
				this.idx = idx;
			}
			@Override
			public String toString() {
				return String.format("[n=%s, idx=%s]", n, idx);
			}
    	}
    	Number[] numbers = new Number[input.length];
    	for (int i = 0; i < input.length; i++) {
    		numbers[i] = new Number(input[i], i+1);
		}
    	Comparator<Number> comparator = new Comparator<Number>() {
			@Override
			public int compare(Number n1, Number n2) {
				return n1.n - n2.n;
			}
		};
		Arrays.sort(numbers, comparator);
		Number key = new Number(-1, -1);
		for (int i = 0; i < numbers.length; i++) {
			Number num = numbers[i];
			int diff = target - num.n;
			if (diff > num.n) {
				key.n = diff;
				int idx = Arrays.binarySearch(numbers, key, comparator);
				if (idx > i) {
					result[0] = num.idx;
					result[1] = numbers[idx].idx;
					break;
				}
			}
			else if (diff == num.n) {
				key.n = diff;
				int idx = Arrays.binarySearch(numbers, key, comparator);
				if (idx == i) {
					if (i < numbers.length - 1 && numbers[i + 1].n == num.n) {
						result[0] = num.idx;
						result[1] = numbers[i+1].idx;
						break;
					}
					else if (i > 0 && numbers[i - 1].n == num.n) {
						result[0] = numbers[i-1].idx;
						result[1] = num.idx;
						break;
					}
				}
				else {
					result[0] = num.idx;
					result[1] = numbers[idx].idx;
					break;
				}
			}
		}
        
		Arrays.sort(result);
        return result;
    }
}